package com.leetcode.算法策略相关.回溯;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author: xiaomi
 * @date: 2021/2/17
 * @description: 剑指 Offer 38. 字符串的排列
 * https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
 * 恢复 这个操作很难想到
 */
public class B_剑指Offer38_字符串的排列 {

	public static void main(String[] args) {
		B_剑指Offer38_字符串的排列 action = new B_剑指Offer38_字符串的排列();
		test1(action);
        test2(action);
	}

	public static void test1(B_剑指Offer38_字符串的排列 action) {
		//200
		String s = "abcd";
		String[] res = action.permutation(s);
		System.out.println("res = " + Arrays.toString(res));
	}

	public static void test2(B_剑指Offer38_字符串的排列 action) {
		//200
		String s = "abc";
		String[] res = action.permutation(s);
		System.out.println("res = " + Arrays.toString(res));
	}

	/**
	 * 这道题确实是适合递归的
	 * 由于考虑到 s 中大概率存在重复的字符，所以用 set 暂存，之后转 String[]
	 * --
	 * 中间确实由于 考虑到 copyArr 的重复创建，导致时间复杂度大大增大。
	 * 但是又想不到替代的方案。。。
	 * --
	 * 拿着 abcd 模拟了一遍，终于找到了可以不用 copyArray 的替代方案。
	 * 但是居然会重复！模拟的有问题。
	 * abcd ,abdc, adbc, adcb ...
	 * --
	 * 看了下题解，虽然还不是很明白，但是有一个地方让我在意的：【恢复交换】
	 * 如果能用 O(1) 的恢复交换替代 O(n) 的时间复杂度和 O(n) 的空间复杂度
	 * 应该就能解决问题了！！！
	 *
	 * @param s
	 * @return
	 */
	public String[] permutationWrongMock(String s) {
		Set<String> set = new HashSet<>();
		char[] chars = s.toCharArray();
		int len = chars.length;

		getArrange(0, set, chars, len);

		int size = set.size();
		String[] res = new String[size];
		int index = 0;
		for (String item :
				set) {
			res[index++] = item;
		}
		return res;
	}

	private void getArrange(int index, Set<String> set, char[] chars, int len) {
		if (index == len) {
			return;
		}

		int ni = index + 1;
		if (ni == len) {
			set.add(new String(chars));
			return;
		} else if (ni + 1 == len) {
			//index == len-2 时
			getArrange(ni, set, chars, len);
			swap(index, ni, chars);
			getArrange(ni, set, chars, len);
			return;
		}

		for (int i = index; i < len; ) {
			getArrange(ni, set, chars, len);
			if (++i < len) {
				swap(index, ni, chars);
			}


//			set.add(new String(chars));
//			swap(index, ni, chars);
//			getArrange(ni, set, chars, len);
//			swap(index, ni, chars);
		}
	}

	private void swap(int index1, int index2, char[] chars) {
		char temp = chars[index1];
		chars[index1] = chars[index2];
		chars[index2] = temp;
	}

	/**
	 * @param s
	 * @return
	 */
	public String[] permutation(String s) {
		Set<String> set = new HashSet<>();
		char[] chars = s.toCharArray();
		int len = chars.length;

		getArrangeWithRecovery(0, set, chars, len);

		int size = set.size();
		String[] res = new String[size];
		int index = 0;
		for (String item :
				set) {
			res[index++] = item;
		}
		return res;
	}

	/**
	 * 把排列的字符串放入 set 中
	 * 比起原先无法解决问题的 getArrange() 方法多了一个恢复的操作：
	 * 虽然单次遍历时增加了恢复的操作，但是节省了数组的拷贝。
	 * 可见启发：
	 * 重复利用来替换重新创建！！！
	 * --
	 * 通过 模拟，找到了恢复的时机：
	 * 每一次调用 深度+1 后，恢复原来的交换
	 *
	 * @param index
	 * @param set
	 * @param chars
	 * @param len
	 */
	private void getArrangeWithRecovery(int index, Set<String> set, char[] chars, int len) {
		if (index == len) {
			return;
		}
		if (index == len - 1) {
			set.add(new String(chars));
			return;
		}
		int i = index + 1;
		getArrangeWithRecovery(i, set, chars, len);
		for (; i < len; i++) {
			swap(i, index, chars);
			if (!set.contains(new String(chars))){
				//增加剪枝的功能
				getArrangeWithRecovery(index + 1, set, chars, len);
			}
			//恢复
			swap(i, index, chars);
		}

	}
}
